import java.util.*;


public class Solution1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        TreeNode root = chonggou(preOrder,inOrder);
        if(root == null) {
            return new int[0];
        }
        Queue<TreeNode> s = new LinkedList<>();
        s.offer(root);
        while(!s.isEmpty()) {
            int size = s.size();
            for(int i = 0;i<size;i++) {
                TreeNode cur = s.poll();
                if(i == size-1) {
                    list.add(cur.val);
                } 
                if(cur.left != null) {
                    s.offer(cur.left);
                }
                if(cur.right != null) {
                    s.offer(cur.right);
                }
            }
        }
        int[] ret = new int[list.size()];
        for(int i = 0;i<list.size();i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
    //重构二叉树
    private TreeNode chonggou(int[] pre,int[] in) {
        if(pre.length != in.length) {
            return null;
        }
        if(pre.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0;i < in.length;i++) {
            if(in[i] == pre[0]) {
                root.left = chonggou(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right = chonggou(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return root;
    }
}